
@BOOK{KS2011:Expander,
  title = {Expander Families and Cayley Graphs},
  publisher = {Oxford University Press},
  year = {2011},
  author = {Mike Krebs and Anthony Shaheen},
  isbn = {978-0-19-976711-3},
  keywords = {expander},
  owner = {peterrobinson},
  timestamp = {2011.12.19}
}

@ARTICLE{G1998:Chernoff,
  author = {David Gillman},
  title = {A {C}hernoff Bound for Random Walks on Expander Graphs},
  journal = {SIAM J. Comput.},
  year = {1998},
  volume = {27},
  pages = {1203-1220},
  number = {4},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  ee = {http://dx.doi.org/10.1137/S0097539794268765},
  keywords = {expanders}
}

@BOOK{MU2005:Probability,
  title = {Probability and computing - randomized algorithms and probabilistic
	analysis},
  publisher = {Cambridge University Press},
  year = {2005},
  author = {Michael Mitzenmacher and Eli Upfal},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  isbn = {978-0-521-83540-4},
  keywords = {textbook}
}

@BOOK{L1994:Discrete,
  title = {Discrete groups, expanding graphs and invariant
measures, volume 125 of Progress in Mathematics},
  publisher = {Birkhäuser},
  year = {1994},
  author = {Alexander Lubotzky},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  keywords = {textbook}
}

@book{S1998:Universal,
  author    = {Christian Scheideler},
  title     = {Universal Routing Strategies for Interconnection Networks},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1390},
  year      = {1998},
  isbn      = {3-540-64505-5},
  ee        = {http://dx.doi.org/10.1007/BFb0052928},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@BOOK{AA2009:Number,
  title = {Number Theory: Structures, Examples, and Problems},
  publisher = {Birkh\"auser Boston},
  year = {2009},
  author = {Titu Andreescu and Dorin Andrica},
  edition = {first},
  keywords = {textbook, numbertheory}
}

@BOOK{MR1995:Randomized,
  title = {Randomized Algorithms},
  publisher = {Cambridge University Press},
  year = {1995},
  author = {Rajeev Motwani and Prabhakar Raghavan},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  isbn = {0-521-47465-5}
}

@INPROCEEDINGS{APRU2012:Towards,
  author = {Augustine, John and Pandurangan, Gopal and Robinson, Peter and Upfal,
	Eli},
  title = {Towards Robust and Efficient Computation in Dynamic Peer-to-Peer
	Networks},
  booktitle = {SODA},
  year = {2012},
  groups = {private},
  interhash = {a86492a9c0977e23dbc23bb84b88effe},
  intrahash = {0a5065f448ef45870fffb1b67baa9c62},
  keywords = {myown},
  owner = {peterrobinson},
  timestamp = {2011-12-15 09:01:44},
  username = {monoid}
}


@book{AW04,
  author = {Hagit Attiya and Jennifer Welch},
  title = {Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition)},
  publisher = {John Wiley Interscience},
  year = {2004},
  month = {March},
  isbn = {0-471-453242}
}

@article{DemboZ98,
author = {A. Dembo and O. Zeitouni},
title = {Large deviations techniques and applications},
journal = {Elearn},
year = {1998},
masid = {1927814}
}

@book{grinstead1997introduction,
  title={Introduction to probability},
  author={Grinstead, C.M. and Snell, J.L.},
  isbn={9780821807491},
  lccn={97008126},
  url={http://books.google.com/books?id=14oq4uWGCkwC},
  year={1997},
  publisher={American Mathematical Society}
}


@inproceedings{KhanKMPT08,
 author = {Khan, Maleq and Kuhn, Fabian and Malkhi, Dahlia and Pandurangan, Gopal and Talwar, Kunal},
 title = {Efficient distributed approximation algorithms via probabilistic tree embeddings},
 booktitle = {Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing},
 series = {PODC '08},
 year = {2008},
 isbn = {978-1-59593-989-0},
 location = {Toronto, Canada},
 pages = {263--272},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1400751.1400787},
 doi = {http://doi.acm.org/10.1145/1400751.1400787},
 acmid = {1400787},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed approximation, generalized steiner forests, least element lists, metric spaces, network optimization, probabilistic tree embeddings},
} 

@article{AoyamaS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Book{ Pel00,
  author = "David Peleg",
  title = "Distributed Computing: A Locality-Sensitive Approach",
  publisher = "SIAM Society for Industrial and Applied Mathematics Monographs on Discrete Mathematics ans Applications",
  address = "Philadelphia",
  year = "2000",
  isbn = "0-89871-464-8" 
}

@ARTICLE{FLP85,
  author =	 "Michael J. Fischer and Nancy A. Lynch and
                  M. S. Paterson",
  title =	 "Impossibility of Distributed Consensus with one
                  Faulty Process",
  journal =	 "Journal of the ACM",
  volume =	 32,
  number =	 2,
  year =	 1985,
  month =	 apr,
  pages =	 "374--382",
}

@Article{AT98,
  author    = {Marcos Kawazoe Aguilera and
               Sam Toueg},
  title     = {A Simple Bivalency Proof that t-Resilient Consensus
               Requires t+1 Rounds},
  journal   = {Inf. Process. Lett.},
  volume    = {71},
  number    = {3--4},
  year      = {1999},
  pages     = {155--158},
  ee        = {http://dx.doi.org/10.1016/S0020-0190(99)00100-3},
}

@inproceedings{KSSV06,
  author    = {Valerie King and
               Jared Saia and
               Vishal Sanwalani and
               Erik Vee},
  title     = {Towards Secure and Scalable Computation in Peer-to-Peer
               Networks},
  booktitle = {FOCS},
  year      = {2006},
  pages     = {87-98}
}

@inproceedings{KOM11,
 author = {Kuhn, Fabian and Oshman, Rotem and Moses, Yoram},
 title = {Coordinated consensus in dynamic networks},
 booktitle = {Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {1--10},
 numpages = {10},
 acmid = {1993808},
 publisher = {ACM},
} 

@article{Upfal94,
  author    = {Eli Upfal},
  title     = {Tolerating a Linear Number of Faults in Networks of Bounded
               Degree},
  journal   = {Inf. Comput.},
  volume    = {115},
  number    = {2},
  year      = {1994},
  pages     = {312-320},
  ee        = {http://dx.doi.org/10.1006/inco.1994.1099},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DPPU88,
  author    = {Cynthia Dwork and
               David Peleg and
               Nicholas Pippenger and
               Eli Upfal},
  title     = {Fault Tolerance in Networks of Bounded Degree},
  journal   = {SIAM J. Comput.},
  volume    = {17},
  number    = {5},
  year      = {1988},
  pages     = {975-988},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CH:PODC10,
 author = {Censor Hillel, Keren and Shachnai, Hadas},
 title = {Partial information spreading with application to distributed maximum coverage},
 booktitle = {Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '10},
 year = {2010},
 isbn = {978-1-60558-888-9},
 location = {Zurich, Switzerland},
 pages = {161--170},
 numpages = {10},
 url = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 doi = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 acmid = {1835739},
 publisher = {ACM},
} 

@inproceedings{ARS07,
  author    = {James Aspnes and
               Navin Rustagi and
               Jared Saia},
  title     = {Worm Versus Alert: Who Wins in a Battle for Control of a
               Large-Scale Network?},
  booktitle = {OPODIS},
  year      = {2007},
  pages     = {443-456},
  crossref  = {DBLP:conf/opodis/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BBCES2006,
  author    = {Amitabha Bagchi and
               Ankur Bhargava and
               Amitabh Chaudhary and
               David Eppstein and
               Christian Scheideler},
  title     = {The Effect of Faults on Network Expansion},
  journal   = {Theory Comput. Syst.},
  volume    = {39},
  number    = {6},
  year      = {2006},
  pages     = {903-928},
  ee        = {http://dx.doi.org/10.1007/s00224-006-1349-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Cohen97,
  author    = {Edith Cohen},
  title     = {Size-Estimation Framework with Applications to Transitive
               Closure and Reachability},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {3},
  year      = {1997},
  pages     = {441-453},
  ee        = {http://dx.doi.org/10.1006/jcss.1997.1534},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{MAS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{LS03,
author={Law, C. and Siu, K.-Y.},
booktitle={INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies}, title={Distributed construction of random expander networks},
year={2003},
month={march-3 april},
volume={3},
number={},
pages={ 2133 - 2143 vol.3},
}

@inproceedings{DGMSS11,
  author    = {Benjamin Doerr and
               Leslie Ann Goldberg and
               Lorenz Minder and
               Thomas Sauerwald and
               Christian Scheideler},
  title     = {Stabilizing consensus with the power of two choices},
  booktitle = {SPAA},
  year      = {2011},
  pages     = {149-158},
}

BibTeX | EndNote | ACM Ref

@article{KS10,
 author = {King, Valerie and Saia, Jared},
 title = {Breaking the {$O(n^2)$} bit barrier: Scalable byzantine agreement with an adaptive adversary},
 journal = {J. ACM},
 issue_date = {July 2011},
 volume = {58},
 issue = {4},
 month = {July},
 year = {2011},
 issn = {0004-5411},
 pages = {18:1--18:24},
 articleno = {18},
 numpages = {24},
 publisher = {ACM},
} 


@inproceedings{KSS06,
  author    = {Valerie King and
               Jared Saia and
               Vishal Sanwalani and
               Erik Vee},
  title     = {Scalable leader election},
  booktitle = {SODA},
  year      = {2006},
  pages     = {990-999},
}

@article{KKKSS10,
  author    = {Bruce M. Kapron and
               David Kempe and
               Valerie King and
               Jared Saia and
               Vishal Sanwalani},
  title     = {Fast asynchronous Byzantine agreement and leader election
               with full information},
  journal   = {ACM Transactions on Algorithms},
  volume    = {6},
  number    = {4},
  year      = {2010},
}

@Book{Lyn96,
  author =	 {Nancy Lynch},
  title =	 {Distributed Algorithms},
  publisher =	 {Morgan Kaufman Publishers, Inc.},
  address =      {San Francisco, USA},
  year =	 {1996},
}

@article{Dolev82,
  author    = {Danny Dolev},
  title     = {The Byzantine Generals Strike Again},
  journal   = {J. Algorithms},
  volume    = {3},
  number    = {1},
  year      = {1982},
  pages     = {14-30},
}

@article{PSL80,
  author    = {Marshall C. Pease and
               Robert E. Shostak and
               Leslie Lamport},
  title     = {Reaching Agreement in the Presence of Faults},
  journal   = {J. ACM},
  volume    = {27},
  number    = {2},
  year      = {1980},
  pages     = {228-234},
}

@misc{Cloudmark,
  author  = {Cloudmark Inc., Website of},
  title = {http://cloudmark.com/}
}

@article{SGG02,
  author    = {P. Krishna Gummadi and
               Stefan Saroiu and
               Steven D. Gribble},
  title     = {A measurement study of Napster and Gnutella as examples
               of peer-to-peer file sharing systems},
  journal   = {Computer Communication Review},
  volume    = {32},
  number    = {1},
  year      = {2002},
  pages     = {82},
}

@inproceedings{SW02,
 author = {Sen, Subhabrata and Wang, Jia},
 title = {Analyzing peer-to-peer traffic across large networks},
 booktitle = {Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment},
 series = {IMW '02},
 year = {2002},
 isbn = {1-58113-603-X},
 location = {Marseille, France},
 pages = {137--150},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{SR06,
 author = {Stutzbach, Daniel and Rejaie, Reza},
 title = {Understanding churn in peer-to-peer networks},
 booktitle = {Proceedings of the 6th ACM SIGCOMM conference on Internet measurement},
 series = {IMC '06},
 year = {2006},
 isbn = {1-59593-561-4},
 location = {Rio de Janeriro, Brazil},
 pages = {189--202},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{BG93,
  author    = {Piotr Berman and
               Juan A. Garay},
  title     = {Fast Consensus in Networks of Bounded Degree},
  journal   = {Distributed Computing},
  volume    = {7},
  number    = {2},
  year      = {1993},
  pages     = {67-73},
}

@inproceedings{Canny02,
  author    = {John F. Canny},
  title     = {Collaborative Filtering with Privacy},
  booktitle = {IEEE Symposium on Security and Privacy},
  year      = {2002},
  pages     = {45-57},
}

@article{DBGWK06,
  author    = {Souptik Datta and
               Kanishka Bhaduri and
               Chris Giannella and
               Ran Wolff and
               Hillol Kargupta},
  title     = {Distributed Data Mining in Peer-to-Peer Networks},
  journal   = {IEEE Internet Computing},
  volume    = {10},
  number    = {4},
  year      = {2006},
  pages     = {18-26},
}


@article{VAS04,
 author = {Vlachos, Vasileios and Androutsellis-Theotokis, Stephanos and Spinellis, Diomidis},
 title = {Security applications of peer-to-peer networks},
 journal = {Comput. Netw.},
 volume = {45},
 issue = {2},
 month = {June},
 year = {2004},
 issn = {1389-1286},
 pages = {195--205},
 numpages = {11},
 publisher = {Elsevier North-Holland, Inc.},
 address = {New York, NY, USA},
} 

@inproceedings{MS05,
  author = {David J. Malan and Michael D. Smith},
  booktitle = {WORM},
  editor = {Vijay Atluri and Angelos D. Keromytis},
  pages = {72-80},
  publisher = {ACM Press},
  title = {Host-based detection of worms through peer-to-peer cooperation.},
  year = 2005,
}

@inproceedings{PRU01,
  author    = {Gopal Pandurangan and
               Prabhakar Raghavan and
               Eli Upfal},
  title     = {Building Low-Diameter {P2P} Networks},
  booktitle = {FOCS},
  year      = {2001},
  pages     = {492-499},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article {AS09,
   author = {Awerbuch, Baruch and Scheideler, Christian},
   title = {Towards a Scalable and Robust {DHT}},
   journal = {Theory of Computing Systems},
   publisher = {Springer New York},
   issn = {1432-4350},
   keyword = {Computer Science},
   pages = {234-260},
   volume = {45},
   issue = {2},
   year = {2009}
}

@inproceedings{FS02,
  author    = {Amos Fiat and
               Jared Saia},
  title     = {Censorship resistant peer-to-peer content addressable networks},
  booktitle = {SODA},
  year      = {2002},
  pages     = {94-103},
}
@inproceedings{NW03,
  author    = {Moni Naor and
               Udi Wieder},
  title     = {A Simple Fault Tolerant Distributed Hash Table},
  booktitle = {IPTPS},
  year      = {2003},
  pages     = {88-97},
  crossref  = {DBLP:conf/iptps/2003},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{HK03,
  author = {Kirsten Hildrum and John Kubiatowicz},
  booktitle = {DISC},
  pages = {321-336},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks.},
  volume = 2848,
  year = 2003,
}
@inproceedings{Scheideler05,
  author    = {Christian Scheideler},
  title     = {How to spread adversarial nodes?: rotate!},
  booktitle = {STOC},
  year      = {2005},
  pages     = {704-713},
  ee        = {http://doi.acm.org/10.1145/1060590.1060694},
  crossref  = {DBLP:conf/stoc/2005},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BCF09,
  author    = {Herv{\'e} Baumann and
               Pierluigi Crescenzi and
               Pierre Fraigniaud},
  title     = {Parsimonious flooding in dynamic graphs},
  booktitle = {PODC},
  year      = {2009},
  pages     = {260-269},
}

@ARTICLE{APRU11,
   author = {{Augustine}, J. and {Pandurangan}, G. and {Robinson}, P. and 
	{Upfal}, E.},
    title = "{Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks}",
  journal = {ArXiv e-prints},
archivePrefix = "arXiv",
   eprint = {1108.0809},
 primaryClass = "cs.DS",
 keywords = {Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing},
     year = 2011,
    month = aug,
   adsurl = {http://adsabs.harvard.edu/abs/2011arXiv1108.0809A},
  adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}

@inproceedings{FPJKA07,
  author    = {Jarret Falkner and
               Michael Piatek and
               John P. John and
               Arvind Krishnamurthy and
               Thomas E. Anderson},
  title     = {Profiling a million user dht},
  booktitle = {Internet Measurement Comference},
  year      = {2007},
  pages     = {129-134},
  ee        = {http://doi.acm.org/10.1145/1298306.1298325},
}

@inproceedings{GKLL09,
  author    = {Roxana Geambasu and
               Tadayoshi Kohno and
               Amit A. Levy and
               Henry M. Levy},
  title     = {Vanish: Increasing Data Privacy with Self-Destructing Data},
  booktitle = {USENIX Security Symposium},
  year      = {2009},
  pages     = {299-316},
  crossref  = {DBLP:conf/uss/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{AS09,
  author    = {Baruch Awerbuch and
               Christian Scheideler},
  title     = {Towards a Scalable and Robust DHT},
  journal   = {Theory Comput. Syst.},
  volume    = {45},
  number    = {2},
  year      = {2009},
  pages     = {234-260},
  ee        = {http://dx.doi.org/10.1007/s00224-008-9099-9},
}

@inproceedings{PT11,
  author    = {Gopal Pandurangan and
               Amitabh Trehan},
  title     = {Xheal: localized self-healing using expanders},
  booktitle = {PODC},
  year      = {2011},
  pages     = {301-310},
  ee        = {http://doi.acm.org/10.1145/1993806.1993865},
  crossref  = {DBLP:conf/podc/2011},
}


@inproceedings{FSY05,
  author    = {Amos Fiat and
               Jared Saia and
               Maxwell Young},
  title     = {Making Chord Robust to Byzantine Attacks},
  booktitle = {ESA},
  year      = {2005},
  pages     = {803-814},
}

@inproceedings{Hae11,
  author    = {Bernhard Haeupler},
  title     = {Analyzing network coding gossip made easy},
  booktitle = {STOC},
  year      = {2011},
  pages     = {293-302},
  ee        = {http://doi.acm.org/10.1145/1993636.1993676},
}

@inproceedings{OW05,
  author    = {Regina O'Dell and
               Roger Wattenhofer},
  title     = {Information dissemination in highly dynamic graphs},
  booktitle = {DIALM-POMC},
  year      = {2005},
  pages     = {104-110},
  ee        = {http://doi.acm.org/10.1145/1080810.1080828},
}

@article{KSW10,
  author    = {Fabian Kuhn and
               Stefan Schmid and
               Roger Wattenhofer},
  title     = {Towards worst-case churn resistant peer-to-peer systems},
  journal   = {Distributed Computing},
  volume    = {22},
  number    = {4},
  year      = {2010},
  pages     = {249-267},
}


@incollection {SS09,
   author = {Scheideler, Christian and Schmid, Stefan},
   affiliation = {Technische Universität München Institut für Informatik D-85748 Garching Germany},
   title = {A Distributed and Oblivious Heap},
   booktitle = {Automata, Languages and Programming},
   series = {Lecture Notes in Computer Science},
   publisher = {Springer Berlin / Heidelberg},
   keyword = {Computer Science},
   pages = {571-582},
   volume = {5556},
   year = {2009}
}


@inproceedings{CRW11,
 author = {Chung, Hyun Chul and Robinson, Peter and Welch, Jennifer L.},
 title = {Optimal regional consecutive leader election in mobile ad-hoc networks},
 booktitle = {Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing},
 series = {FOMC '11},
 year = {2011},
 isbn = {978-1-4503-0779-6},
 location = {San Jose, California},
 pages = {52--61},
 numpages = {10},
  ee        = {http://dx.doi.org/10.1007/s00446-010-0099-z},
 doi = {http://doi.acm.org/10.1145/1998476.1998485},
 acmid = {1998485},
 publisher = {ACM},
} 


@inproceedings{avin1, 
author = {Chen Avin and Michael Borokhovich and Keren Censor-Hillel and Zvi Lotker},
title = {Order Optimal Information Spreading Using Algebraic Gossip},
booktitle = {ACM  PODC},
year = {2011},
pages = {363-372}
}


@inproceedings{avin2,
author = {Michael Borokhovich and Chen Avin and Zvi Lotker},
title = {Tight Bounds for Algebraic Gossip on Graphs},
booktitle = {IEEE ISIT},
year = {2010}
}


  
@article{kuhn-survey,
author = {F. Kuhn and R. Oshman},
title = {Dynamic networks: Models and algorithms},
journal ={SIGACT News},
volume = {42(1)},
pages = {82-96}, 
 year = {2011}
} 

@inproceedings{kuhn+lo:dynamic,
 author = {Kuhn, Fabian and Lynch, Nancy and Oshman, Rotem},
 title = {Distributed computation in dynamic networks},
 booktitle = {ACM STOC},
 year = {2010},
 pages = {513--522},
} 

@article{chernoff,
  title = {Asymptotic efficiency for tests based on the sum of observations},
  author = {H. Chernoff},
  journal = {Math. Stat.},
  year = {1952},
}

@article{hoeffding,
  title = {Probability for sums of bounded random variables},
  author = {W. Hoeffding},
  journal = {Journal of American Statistical Association},
  year = {1963},
}

@article{angluin,
  title = {Fast probabilistic algorithms for Hamiltonian circuits and matchings},
  author = {D. Angluin and L.G. Valiant},
  journal = {Journal of Computer and System Sciences},
  year = {1979},
}

@article{jain+ms:steiner,
  title = {Packing Steiner trees},
  author = {K. Jain and M. Mahdian and M. Salavatipour},
  journal = {SODA},
  year = {2003},
}

@article{cheriyan+s:steiner,
  title = {Hardness and Approximation Results for Packing Steiner Trees},
  author = {J. Cheriyan and M. Salavatipour},
  journal = {Algorithmica},
  year = {2006},
}

@article{charikar+ccdgg:steiner,
  title = {Approximation Algorithms for Directed Steiner Problems},
  author = {M. Charikar and C. Chekuri and T. Cheung and Z. Dai and A. Goel and S. Guha},
  journal = {Journal of Algorithms},
  year = {1998},
}

@article{lau:steiner,
  title = {An approximate max-steiner-tree-packing min-steiner-cut theorem},
  author = {L.C. Lau},
  journal = {FOCS},
  year = {2004},
}

@article{guruswami+krsy,
  title = {Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems},
  author = {V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis},
  journal = {STOC},
  year = {1999},
}

@inproceedings{haeupler:gossip,
 author = {Haeupler, Bernhard},
 title = {Analyzing network coding gossip made easy},
 booktitle = {ACM STOC},
 year = {2011},
 pages = {293--302},
} 

@inproceedings{haeupler+k:dynamic,
 author = {Haeupler, Bernhard and Karger, David},
 title = {Faster information dissemination in dynamic networks via network coding},
 booktitle = {ACM PODC},
 year = {2011},
 pages = {381--390},
} 

@article{gafni:dynamic,
  title = {End-to-end communication in unreliable networks},
  author = {E. Gafni and Y. Afek},
  journal = {PODC},
  year = {1988}
}

@INPROCEEDINGS{afek+gr:slide,
    author = {Yehuda Afek and Eli Gafni and Adi Rosen},
    title = {The Slide Mechanism with Applications in Dynamic Networks},
    booktitle = {ACM PODC},
    year = {1992},
    pages = {35--46}
}

@article{awerbuch:adversarial,
  title = {Simple Routing Strategies for Adversarial Systems},
  author = {B. Awerbuch and P. Berenbrink and A. Brinkmann and C. Scheideler},
  journal = {FOCS},
  year = {2002}
}

@article{awerbuch:icalp,
  title = {Anycasting in adversarial systems: Routing and admission control},
  author = {B. Awerbuch and A. Brinkmann and C. Scheideler},
  journal = {ICALP},
  year = {2003}
}

@book{leighton:book,
author = "Leighton, F. T.",
title = "Introduction to Parallel Algorithms and Architectures: Arrays,
Trees, and Hypercubes",
publisher = "Morgan-Kaufmann",
year = "1991",
address = "San Mateo, CA",
}



@article{topkis:disseminate,
 author = {Topkis, Donald M.},
 title = {Concurrent Broadcast for Information Dissemination},
 journal = {IEEE Trans. Softw. Eng.},
 volume = {11},
 issue = {10},
 month = {October},
 year = {1985},
 pages = {1107--1112},
} 


@book{dolev:stabilize,
 author = {Dolev, Shlomi},
 title = {Self-stabilization},
 year = {2000},
 publisher = {MIT Press},
 address = {Cambridge, MA, USA},
}

@article{gafni+b:link-reversal,
author = "Gafni, E. and Bertsekas, B.",
title = "Distributed algorithms for generating loop-free routes in networks with
frequently changing topology",
journal = "IEEE Trans. Comm.",
volume = "29",
number = "1",
pages = "11–18",
year = "1981",
}

@INPROCEEDINGS{afek+ag:dynamic,                                                                            
AUTHOR = "Yehuda Afek and Baruch Awerbuch and Eli Gafni",
TITLE = "Applying Static Network Protocols to Dynamic Networks",
booktitle = "FOCS'87", 
PAGES = {358-370}, 
YEAR = {1987},
}      

@INPROCEEDINGS{awerbuch+pps:dynamic,
AUTHOR = "Baruch Awerbuch and Boaz Patt-Shamir and David Peleg and Michael E. Saks",
TITLE = "Adapting to Asynchronous Dynamic Networks",
booktitle = "STOC'92",
PAGES = {557-570},
YEAR = {1992}  }

@inproceedings{awerbuch+l:flow,
author = "Awerbuch, B. and Leighton, F. T.",
title = "Improved Approximation Algorithms for the Multi-commodity
Flow Problem and Local Competitive Routing in Dynamic Networks",
booktitle = "ACM STOC", 
year = "1994",
month = "May",
pages = "487--496",
}

@inproceedings{awerbuch+bbs:route,
author = "Awerbuch, B. and Berenbrink, P. and Brinkmann, A. and Scheideler, C.",
title = "Simple Routing Strategies for Adversarial Systems",
booktitle = "IEEE FOCS",
year = "2001",
pages = "158--167",
}

@inproceedings{jia+rs:adhoc,
author = "Jia, L. and Rajaraman, R. and Scheideler, C.",
title = "On Local Algorithms for Topology Control and Routing in Ad Hoc Networks",
booktitle = "ACM SPAA",
year = "2003",
month = "June",
pages = "220--229",
}

@INPROCEEDINGS{awerbuch+bs:anycast,
AUTHOR = "Baruch Awerbuch and André Brinkmann and Christian Scheideler",
TITLE = "Anycasting in Adversarial Systems: Routing and Admission Control.",
booktitle = "ICALP'03",
PAGES = {1153-1168},
YEAR = {2003}  }

@article{alon+blp:radio,
author = "Alon, N. and Bar-Noy, A. and Linial, N. and Peleg, D.",
title = "A Lower Bound for Radio Broadcast",
journal = "Journal of Computer and System Sciences",
volume = "43",
year = "1991",
pages = "290--298",
}

@INPROCEEDINGS{clementi+ms:radio,
AUTHOR = "Andrea E. F. Clementi and Angelo Monti and Riccardo Silvestri",
TITLE = "Distributed multi-broadcast in unknown radio networks.",
booktitle = "PODC'01",
PAGES = {255-264},
YEAR = {2001}  }

@inproceedings{bar-yehuda+gi:radio,
 author = {Bar-Yehuda, R. and Goldreich, O. and Itai, A.},
 title = {On the time-complexity of broadcast in radio networks: an exponential gap between determinism and randomization},
 booktitle = {ACM PODC},
 year = {1987},
 pages = {98--108},
} 

@article{ahlswede+cly:coding,
author = "Ahlswede, R. and Cai, N. and Li, S. and Yeung, R.",
title = "Network information flow",
journal = "Transactions on Information Theory",
volume = "46",
number = "4",
pages = "1204--1216", 
year = "2000",
}

@inproceedings{zosin+k:steiner,
author = "Zosin, L. and Khuller, S.",
title = "On Directed {Steiner} Trees",
booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on
Discrete Algorithms",
year = "2002",
month = "January",
}

@INPROCEEDINGS{sanders+et:flow,
    author = {Peter Sanders and Sebastian Egner and Ludo Tolhuizen},
    title = {Polynomial Time Algorithms for Network Information Flow},
    booktitle = {ACM SPAA},
    year = {2003},
    pages = {286--294}
}

@inproceedings{kempe1, 
author = {D. Kempe and J. Kleinberg},
title ={Protocols and Impossibility Results for Gossip-Based Communication Mechanisms}, 
booktitle = {IEEE FOCS},
year = {2002}
}

@inproceedings{chen-spaa,
  author    = {J. Chen and G. Pandurangan},
  title     = {Optimal Gossip-based Aggregate Computation},
  booktitle = {SPAA},
  year      = {2010},
  pages     = {124-133}
}

@inproceedings{demers,
 author = {Alan Demers and Dan Greene and Carl Hauser and Wes Irish and John Larson and Scott Shenker and Howard Sturgis and Dan Swinehart and Doug Terry},
 title = {Epidemic algorithms for replicated database maintenance},
 booktitle = {PODC},
 year = {1987},
 pages = {1--12},
 }

@inproceedings{shah,
 author = {Damon Mosk-Aoyama and Devavrat Shah},
 title = {Computing separable functions via gossip},
 booktitle = {PODC},
 year = {2006},
 pages = {113--122}
 }

@inproceedings{karp,
 author = {R. M. Karp and C. Schindelhauer and S. Shenker and B. V\"{o}cking},
 title = {Randomized rumor spreading},
 booktitle = {FOCS},
 year = {2000},
 isbn = {0-7695-0850-2},
 pages = {565--574},
 publisher = {},
 address = {},
 }

@inproceedings{kempe,
author ={D. Kempe and A. Dobra and J. Gehrke},
title={Gossip-based Computation of
Aggregate Information},
booktitle={FOCS},
year={2003},
pages={482--491},
}

@article{boyd,
 author = {S. Boyd and A. Ghosh and B. Prabhakar and D. Shah},
 title = {Randomized gossip algorithms},
 journal = {IEEE Trans. on Infor. Theory},
 volume = {52},
 number = {6},
 year = {2006},
 pages = {2508--2530}
  }

@INPROCEEDINGS{berenbrink+ceg:gossip,
AUTHOR = "Petra Berenbrink and Jurek Czyzowicz and Robert Els{\"{a}}sser and Leszek Gasieniec",
TITLE = "Efficient Information Exchange in the Random Phone-Call Model",
booktitle = "ICALP",
PAGES = {127-138},
YEAR = {2010}  }

@ARTICLE{bar-noy+gns:multicast,
AUTHOR = "Amotz Bar-Noy and Sudipto Guha and Joseph Naor and Baruch Schieber",
TITLE = "Message Multicasting in Heterogeneous Networks.",
JOURNAL = "SIAM J. Comput.",
PAGES = {347-358},
YEAR = {2000}  }

@inproceedings{avin+kl:dynamic,
 author = {Avin, Chen and Kouck\'{y}, Michal and Lotker, Zvi},
 title = {How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)},
 booktitle = {ICALP},
 year = {2008},
 pages = {121--132},
} 

@inproceedings{agarwal+c:coding,
title = "On the advantage of Network Coding for Improving Network Throughput",
author = "Agarwal, A. and Charikar, M.",
booktitle = "Information Theory Workshop",
year = "2004",
}

@article{deb+mc:coding,
 author = {Deb, S. and M\'{e}dard, M. and Choute, C.},
 title = {Algebraic gossip: a network coding approach to optimal multiple rumor mongering},
 journal = {IEEE/ACM Trans. Netw.},
 volume = {14},
 month = {June},
 year = {2006},
 pages = {2486--2507},
} 

@inproceedings{LBK02,
  author    = {David Liben-Nowell and
               Hari Balakrishnan and
               David R. Karger},
  title     = {Analysis of the evolution of peer-to-peer systems},
  booktitle = {PODC},
  year      = {2002},
  pages     = {233-242},
  ee        = {http://doi.acm.org/10.1145/571825.571863},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{MNR02,
  author    = {Dahlia Malkhi and
               Moni Naor and
               David Ratajczak},
  title     = {Viceroy: a scalable and dynamic emulation of the butterfly},
  booktitle = {PODC},
  year      = {2002},
  pages     = {183-192},
  ee        = {http://doi.acm.org/10.1145/571825.571857},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{CDG07,
  author    = {Colin Cooper and
               Martin E. Dyer and
               Catherine S. Greenhill},
  title     = {Sampling Regular Graphs and a Peer-to-Peer Network},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {16},
  number    = {4},
  year      = {2007},
  pages     = {557-593},
  ee        = {http://dx.doi.org/10.1017/S0963548306007978},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Kuhn2005self-repairing,
  author    = {Fabian Kuhn and
               Stefan Schmid and
               Roger Wattenhofer},
  title     = {A Self-repairing Peer-to-Peer System Resilient to Dynamic
               Adversarial Churn},
  booktitle = {IPTPS},
  year      = {2005},
  pages     = {13-23},
  ee        = {http://dx.doi.org/10.1007/11558989_2},
  crossref  = {DBLP:conf/iptps/2005},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{JP,
  author    = {Suresh Jagannathan and
               Gopal Pandurangan and
               Siriam Srinivasan},
  title     = {Query Protocols for Highly Resilient Peer-to-Peer Networks},
  booktitle = {ISCA PDCS},
  year      = {2006},
  pages     = {247-252},
  crossref  = {DBLP:conf/ISCApdcs/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book {MR0163361,
    	AUTHOR = {Harris, Theodore E.},
     	TITLE = {The theory of branching processes},
   	 SERIES = {Die Grundlehren der Mathematischen Wissenschaften, Bd. 119},
 	PUBLISHER = {Springer-Verlag},
  	 ADDRESS = {Berlin},
      	YEAR = {1963},
     	PAGES = {xiv+230},
   	MRCLASS = {60.67},
  	MRNUMBER = {0163361 (29 \#664)},
	MRREVIEWER = {P. A. P. Moran},
}


@article{Madras1992255,
title = "Branching random walks on trees",
journal = "Stochastic Processes and their Applications",
volume = "42",
number = "2",
pages = "255 - 267",
year = "1992",
note = "",
issn = "0304-4149",
doi = "10.1016/0304-4149(92)90038-R",
url = "http://www.sciencedirect.com/science/article/pii/030441499290038R",
author = "Neal Madras and Rinaldo Schinazi"
}

@article{benjamini2010trace,
  title={On the trace of branching random walks},
  author={Benjamini, Itai and M{\"u}ller, Sebastian},
  journal={arXiv preprint arXiv:1002.2781},
  year={2010}
}

@inproceedings{cooper2012coalescing,
  title={Coalescing random walks and voting on graphs},
  author={Cooper, Colin and Els{\"a}sser, Robert and Ono, Hirotaka and Radzik, Tomasz},
  booktitle={Proceedings of the 2012 ACM symposium on Principles of distributed computing},
  pages={47--56},
  year={2012},
  organization={ACM}
}

@article{arthreya2005branching,
  title={Branching-coalescing particle systems},
  author={Arthreya, Siva R and Swart, Jan M},
  journal={Probability theory and related fields},
  volume={131},
  number={3},
  pages={376--414},
  year={2005},
  publisher={Springer}
}

@article{sun2008brownian,
  title={The Brownian net},
  author={Sun, Rongfeng and Swart, Jan M},
  journal={The Annals of Probability},
  volume={36},
  number={3},
  pages={1153--1208},
  year={2008},
  publisher={Institute of Mathematical Statistics}
}

@article{matthews1988covering,
  title={Covering problems for Brownian motion on spheres},
  author={Matthews, Peter},
  journal={The Annals of Probability},
  pages={189--199},
  year={1988},
  publisher={JSTOR}
}

@inproceedings{mihail1989conductance,
  title={Conductance and convergence of Markov chains-A combinatorial treatment of expanders},
  author={Mihail, Milena},
  booktitle={Foundations of Computer Science, 1989., 30th Annual Symposium on},
  pages={526--531},
  year={1989},
  organization={IEEE}
}





